package binary_tree.LeetCode;


import java.util.ArrayDeque;
import java.util.Deque;

/**
 * 判断二叉树是否为完全二叉树
 */
public class Num958 {
    public boolean isCompleteTree(TreeNode root) {
        Deque<TreeNode> deque = new ArrayDeque<>();
        deque.offer(root);
        //判断是否进入第二阶段，引入标记位
        boolean isSecondStep = false;
        while (!deque.isEmpty()) {
            TreeNode r1 = deque.poll();
            if (!isSecondStep) {
                //在第一阶段，每个节点都有左子树和右子树
                if (r1.left != null && r1.right != null) {
                    deque.offer(r1.left);
                    deque.offer(r1.right);
                } else if (r1.left != null) {
                    //此时只有左子树没有右子树，进入第二阶段
                    isSecondStep = true;
                    deque.offer(r1.left);
                } else if (r1.right != null) {
                    //此时遇到了只有右子树没有左子树的节点，return false
                    return false;
                } else {
                    //此时节点没有左子树和右子树，也就是遇到了第一个叶子节点，进入第二阶段
                    isSecondStep = true;
                }
            }else {
                //此时进入第二阶段，只存在叶子节点
                if(r1.left!=null||r1.right!=null){
                    return false;
                }
            }
        }
        return true;
    }
}